COMMENT ⊗   VALID 00002 PAGES 
RECORD PAGE   DESCRIPTION
 00001 00001
 00002 00002	~F83. NESTING.
 00006 ENDMK
⊗;
~F83. NESTING.


	The nesting problem is to decide  whether one contour polygon
is  within another.  Although  easy in the two  polygon case; solving
the nesting  of many  polygons  with respect  to each  other  becomes
n-squared expensive in  either compute time or in memory  space.  The
nesting  solution in  CRE sacrifices memory  for the  sake of greater
speed and requires a 31K array, called the SKY.


	CRE's accumulation  of  a properly  nested  tree of  polygons
depends on the  order of threshold cutting going  from dark to light.
For each polygon there are two  nesting steps: first, the polygon  is
placed in  the  tree of  nested polygons  by  the subroutine  INTREE;
second,   the polygon  is placed in  the SKY array  by the subroutine
named INSKY.


	The SKY array is 216 rows of 289 columns of  18-bit pointers.
The name "SKY"  came about because,  the array  use  to represent the
furthest  away regions or  background, which  in the case  of a robot
vehicle is the real sky  blue. The sky contains vector  pointers; and
would be  more efficient on  a virtual memory  machine that didn't
allocate unused pages of its  address space.  Whereas most  computers
have more  memory containers  than address  space; computer  graphics
and vision  might be easier to program in  a memory with more address
space than physical space; i.e. an almost empty virtual memory.


	The first part of the INTREE routine  finds the surrounder of
a given polygon  by scanning the SKY due east from the uppermost left
pixel of  the given polygon.   The  SON of  a polygon  is always  its
uppermost  left  vector. After  INTREE,    the INSKY  routine  places
pointers  to the vertical vectors  of the given  polygon into the sky
array.


	The second part  of the INTREE  routine checks for  and fixes
up the case  where the new polygon captures a polygon that is already
enclaved. This  only happens when  two or  more levels  of the  image
have blobs that have holes.   The next paragraph explains  the arcane
details of  fixing up the tree links of multi level hole polygons and
the box following that is  a quotation from the appendix  of Krakauer
thesis [3] describing his nesting algorithm.~I1973,800;F8- 27 -